import networkx as nx
import copy

flag = 'f'
extent_mark='ex'
intent_mark='in'

def toBottom(g,atts):
    g.node[-1][intent_mark].update(atts)

def cleanFlags(g,intent):
    for j in g.neighbors(intent):
        if not g.node[j][flag]:
            cleanFlags(g,j)
    g.node[intent][flag]=True

def printLattice(g):
    for n in g.nodes(data=True):
        print n,g.neighbors(n[0])

def addObject(g,intent,object,depth=1):
    if not g.node[intent][flag]:
        return 0
    #print "-"*depth,object,'->',intent,g.node[intent],'=',
    g.node[intent][flag]=False
    g.node[intent][extent_mark].append(object)
    #print g.node[intent]
    for j in g.neighbors(intent):
        addObject(g,j,object,depth+1)


def init_diagram():
    g = nx.DiGraph()
    g.add_node(-1,{intent_mark:set([]),extent_mark:[],flag:True})
    g.add_node(-2,{intent_mark:set([]),extent_mark:[],flag:True})
    g.add_edge(-1,-2)
    return g

def get_maximal_concept(g,intent,generator):
    if len(intent) == 0:
        return -2
    for j in g.neighbors(generator):
        if intent == g.node[j][intent_mark]: # THE CONCEPT ALREADY EXISTS. RETURN THE NODE ID OF THAT CONCEPT
            return j
        elif intent.issubset(g.node[j][intent_mark]): # THE MOST COMMON CASE
            return get_maximal_concept(g,intent,j)
    return generator

def addIntent(g,intent,generator):
    #print '---->',pair,generator
    #    print g.nodes(data=True)
    generator = get_maximal_concept(g,intent,-1)
    #print 'new generator',g.node[generator],generator
    if generator!=-1 and g.node[generator][intent_mark] == intent:
            return generator
    new_parents = []
    for candidate in g.neighbors(generator):
        if not g.node[candidate][intent_mark].issubset(intent):
            cand_inter = g.node[candidate][intent_mark].intersection(intent)
            candidate = addIntent(g,cand_inter,candidate)
        add_parent = True
        for parent in new_parents:
            if g.node[candidate][intent_mark].issubset(g.node[parent][intent_mark]):
                add_parent = False
                break
            elif g.node[parent][intent_mark].issubset(g.node[candidate][intent_mark]):
                del new_parents[new_parents.index(parent)]
        if add_parent:
            new_parents.append(candidate)
    new_id = len(g.nodes())-2

#
    g.add_node(new_id,{extent_mark:copy.copy(g.node[generator][extent_mark]),intent_mark:intent,flag:True})
    #print 'ADDED',new_id,'-',g.node[new_id]
    for parent in new_parents:
        if parent in g[generator]:
            g.remove_edge(generator,parent)
#        print 'O',new_id,parent
        g.add_edge(new_id,parent)
#print 'O',generator,new_id
    g.add_edge(generator,new_id)
    return new_id